#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;


 // Definition for singly-linked list.
  struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==headB){
            return headA;
        }
        
        ListNode* uperpoint = headA;
        ListNode* lowpoint = headB;
        int status0 = 0;
        int status1 = 0;
        while(uperpoint!=NULL&&lowpoint!=NULL){
            if(uperpoint->next==NULL&&status0==0){
                uperpoint = headB;
                status0 = 1;
            }
            if(lowpoint->next==NULL&&status1==0){
                lowpoint = headA;
                status1 = 1;
            }
            if(status0==1&&status1==1&&lowpoint==uperpoint){
                return lowpoint;
            }
            uperpoint = uperpoint->next;
            lowpoint = lowpoint->next;
        }
        return NULL;
    }
};

int main(){
    Solution S;
    ListNode* headA = new ListNode(4);
    headA->next = new ListNode(1);
    headA->next->next = new ListNode(8);
    headA->next->next->next = new ListNode(4);
    headA->next->next->next->next = new ListNode(5);

    ListNode* headB = new ListNode(5);
    headB->next = new ListNode(0);
    headB->next->next = new ListNode(1);
    headB->next->next->next = headA->next->next;

    ListNode* root = S.getIntersectionNode(headA,headB);
    return 0;
}